package leetcode.codetop.腾讯;

import org.junit.Test;


/**
 * @author ：zsy
 * @date ：Created 2021/12/4 11:38
 * @description：https://leetcode-cn.com/problems/multiply-strings/
 */
public class 字符串相乘 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println("987654321 * 123456789 = " + solution.multiply("987654321", "123456789"));
    }

    class Solution {
        public String multiply(String num1, String num2) {
            // 调整num2为乘数，长度尽量短
            if (num2.length() > num1.length()) {
                String tmp = num1;
                num1 = num2;
                num2 = tmp;
            }
            StringBuilder num2_builder = new StringBuilder(num2).reverse();
            String ans = "";
            for (int i = 0; i < num2_builder.length(); i++) {
                char multiplier = num2_builder.charAt(i);
                // 乘数的每一位和被乘数相乘
                StringBuilder cur = multiply0(num1, multiplier);
                // 调整位置
                for (int j = 0; j < i; j++) {
                    cur.append("0");
                }
                // 相加
                ans = add(ans, cur.toString());
            }
            return ans;
        }

        private StringBuilder multiply0(String multiplicand, char multiplier) {
            if (multiplier == '0') return new StringBuilder("0");
            StringBuilder multiplicand_builder = new StringBuilder(multiplicand).reverse();
            StringBuilder ans = new StringBuilder();
            int factor = 0;
            int b = multiplier - '0';
            for (int i = 0; i < multiplicand.length(); i++) {
                int a = multiplicand_builder.charAt(i) - '0';
                int cur = a * b + factor;
                factor = cur / 10;
                ans.append(cur % 10);
            }
            if (factor != 0) {
                ans.append(factor);
            }
            return ans.reverse();
        }

        private String add(String num1, String num2) {
            StringBuilder num1_builder = new StringBuilder(num1).reverse();
            StringBuilder num2_builder = new StringBuilder(num2).reverse();
            StringBuilder ans = new StringBuilder();
            int factor = 0;
            int len1 = num1.length();
            int len2 = num2.length();
            int len = Math.max(len1, len2);
            for (int i = 0; i < len; i++) {
                int a = i >= len1 ? 0 : num1_builder.charAt(i) - '0';
                int b = i >= len2 ? 0 : num2_builder.charAt(i) - '0';
                int sum = a + b + factor;
                factor = sum / 10;
                ans.append(sum % 10);
            }
            if (factor != 0) {
                ans.append(factor);
            }
            return ans.reverse().toString();
        }
    }
}
